package edu.princeton.cs.algs4;

import edu.princeton.cs.stdlib.StdOut;
import edu.princeton.cs.stdlib.StdRandom;

/*************************************************************************
 * Compilation: javac Bipartite.java Dependencies: Graph.java
 * 
 * Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
 * Runs in O(E + V) time.
 * 
 * 
 *************************************************************************/

public class Bipartite {
	private boolean isBipartite; // is the graph bipartite?
	private boolean[] color; // color[v] gives vertices on one side of
								// bipartition
	private boolean[] marked; // marked[v] = true if v has been visited in DFS
	private int[] edgeTo; // edgeTo[v] = last edge on path to v
	private Stack<Integer> cycle; // odd-length cycle

	public Bipartite(Graph G) {
		isBipartite = true;
		color = new boolean[G.V()];
		marked = new boolean[G.V()];
		edgeTo = new int[G.V()];

		for (int v = 0; v < G.V(); v++) {
			if (!marked[v]) {
				// color[v] = false;
				dfs(G, v);
			}
		}
		assert check(G);
	}

	private void dfs(Graph G, int v) {
		marked[v] = true;
		for (int w : G.adj(v)) {

			// short circuit if odd-length cycle found
			if (cycle != null)
				return;

			// found uncolored vertex, so recur
			if (!marked[w]) {
				edgeTo[w] = v;
				color[w] = !color[v];
				dfs(G, w);
			}

			// if v-w create an odd-length cycle, find it
			else if (color[w] == color[v]) {
				isBipartite = false;
				cycle = new Stack<Integer>();
				cycle.push(w); // don't need this unless you want to include
								// start vertex twice
				for (int x = v; x != w; x = edgeTo[x]) {
					cycle.push(x);
				}
				cycle.push(w);
			}
		}
	}

	boolean isBipartite() {
		return isBipartite;
	}

	boolean color(int v) {
		return color[v];
	}

	public Iterable<Integer> cycle() {
		return cycle;
	}

	private boolean check(Graph G) {
		// graph is bipartite
		if (isBipartite) {
			for (int v = 0; v < G.V(); v++) {
				for (int w : G.adj(v)) {
					if (color[v] == color[w]) {
						System.err
								.printf("edge %d-%d with %d and %d in same side of bipartition\n",
										v, w, v, w);
						return false;
					}
				}
			}
		}

		// graph has an odd-length cycle
		else {
			// verify cycle
			int first = -1, last = -1;
			for (int v : cycle()) {
				if (first == -1)
					first = v;
				last = v;
			}
			if (first != last) {
				System.err.printf("cycle begins with %d and ends with %d\n",
						first, last);
				return false;
			}
		}

		return true;
	}

	public static void main(String[] args) {
		// create random bipartite graph with V vertices and E edges; then add F
		// random edges
		int V = Integer.parseInt(args[0]);
		int E = Integer.parseInt(args[1]);
		int F = Integer.parseInt(args[2]);

		Graph G = new Graph(V);
		int[] vertices = new int[V];
		for (int i = 0; i < V; i++)
			vertices[i] = i;
		StdRandom.shuffle(vertices);
		for (int i = 0; i < E; i++) {
			int v = StdRandom.uniform(V / 2);
			int w = StdRandom.uniform(V / 2);
			G.addEdge(vertices[v], vertices[V / 2 + w]);
		}

		// add F extra edges
		for (int i = 0; i < F; i++) {
			int v = (int) (Math.random() * V);
			int w = (int) (Math.random() * V);
			G.addEdge(v, w);
		}

		StdOut.println(G);

		Bipartite b = new Bipartite(G);
		if (b.isBipartite()) {
			StdOut.println("Graph is bipartite");
			for (int v = 0; v < G.V(); v++) {
				StdOut.println(v + ": " + b.color(v));
			}
		} else {
			StdOut.print("Graph has an odd-length cycle: ");
			for (int x : b.cycle()) {
				StdOut.print(x + " ");
			}
			StdOut.println();
		}
	}

}
